#include<iostream>
#include<vector>
#include<stack>
using namespace std;


class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<pair<int, int>> st; // pair<temp, posi>
        vector<int> ans;
        ans.resize(n, 0);
        for (int i = 0; i < n; i++) {
            int tmpTem = temperatures[i];
            int tmpAdd = 1;
            while (!st.empty() && st.top().first < tmpTem) {
                ans[st.top().second] = tmpAdd;
                st.pop();
                tmpAdd++;
            }
            st.push(make_pair(tmpTem, i));
        }
        return ans;
    }
};